package LeetCode_everyDay;

import java.util.ArrayList;
import java.util.List;

/**
 * 658. 找到 K 个最接近的元素
 *
 *  思路： 分为两步：
 *        第一步，先使用二分查找，找出数组中最接近x的数
 *        第二步, 找出后然后使用双指针左右遍历，然后对比，找出最接近的K个数
 *
 */
public class LeetCode658 {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
       int right = binarySearch(arr,x);
       int left = right-1;
       while (k-->0){
           if(left<0){
               right++;
           }else if(right>=arr.length){
               left--;
           }else if(x-arr[left] <= arr[right] -x){
               left--;
           }else {
               right++;
           }
       }
       List<Integer> res = new ArrayList<>();
        for (int i = left+1; i <right ; i++) {
            res.add(arr[i]);
        }
        return res;
    }

    /**
     * 找出数组中最接近X的数
     * @param arr
     * @param x
     * @return
     */
    private int binarySearch(int [] arr, int x){
        int low =0,high = arr.length-1;
        while (low < high){
            int mid = low + (high - low)/2;
            if(arr[mid]>=x){
                high = mid;
            }else {
                low = mid+1;
            }
        }
        return low;
    }
}
